package com.cat.chapter038;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;

/**
 * @author cat
 * @description https://leetcode.cn/problems/VvJkup/
 * @create 2025/7/7 17:43
 * @since JDK17
 */

public class Solution02 {
    List<List<Integer>> answer = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    boolean[] hash = new boolean[10]; // 标记第i个数字是否被使用过

    public List<List<Integer>> permute(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            list.add(0);
        }
        f(nums, 0, nums.length);
        return answer;
    }

    public void f(int[] nums, int cur, int n) {
        if (cur == n) { // 到了最后一个
            answer.add(new ArrayList<>(list));
            return;
        }
        // cur 之前的都被选过了
        for (int i = 0; i < n; i++) {
            if (hash[i]) continue;
            hash[i] = true; // 被使用过了
            list.set(cur, nums[i]); // 给cur位置设置好数字
            f(nums, cur + 1, n);
            hash[i] = false; // 解除使用
        }
    }
}